home *** CD-ROM | disk | FTP | other *** search
/ PCMania 64 / PCMania CD64_1.iso / phy / phy005 / files / articulo.t11 < prev    next >
Encoding:
Text File  |  1997-09-19  |  68.2 KB  |  1 lines

  1.                                                                                      ε             Fast affine texture mapping II (fatmap2.txt)                           ε             --------------------------------------------                                                                                                                ε                                por                                                                                                                                      ∞                          Mats Byggmastar                                                                                                                                ∞                                MRI                                                                                                                                      ∞                     programador 3D en Doomsday                                     ∞                          mri@penti.sit.fi                                                                                                                               ∞                  17 Abril 1997, Jakobstad, Finland                                                                                                                      ∞      Traducido al castellano por Angel Iglesias AKA Matrix / Dosis                                                                                                      ∞                      22 Mayo 1997, Lugo, España                                                                                                                                                                                                                    Eres libre de enviar este documento a cualquier sitio que encuentres                 apropiado que lo conserves sin ninguna modificación.                                 Esta es una información libre, no puedes cobrar nada por ella.                       Las empresas deberán contactar conmigo si parte de este código es                    usado como parte de un producto comercial.                                                                                                                                                                                                                                                                                                    φ  Tabla de contenidos                                                               φ  --------------------                                                                                                                                                   φ  1.  Sobre este documento                                                          φ  2.  Aviso                                                                         φ  3.  Sobre el codigo fuente                                                        φ  4.  Poligonos convexos                                                            φ  5.  Dibujando poligonos convexos                                                  φ  6.  Gradientes de textura constantes y poligonos                                  φ  7.  idiv e imul en coma fija 16:16                                                φ  8.  Funcion ceil() de coma fijo                                                   φ  9.  Precision de subpixel                                                         φ  10. Precision de subtexel                                                         φ  11. Evitando divide overflow en calculos descendentes                             φ  12. Contadores en bucles internos                                                 φ  13. Bucle interno de 8:16 bit                                                     φ  14. Bucle interno con bitmaps de cualquier tamaño                                 φ  15. Bucle interno de 8:15 bit para tiled (embaldosados)                           φ  16. Poligonos por segundo                                                         φ  17. Saludos                                                                                                                                                                                                                                                                                                                                      φ  1.  Sobre este documento                                                          φ  -------------------------                                                                                                                                                    Este documento es la continuación a fatmap.txt publicado el 19 de                    Junio de 1996. El objetivo de este segundo documento es hacer más                    preciso el mapeador de texturas. He omitido los triángulos y me he                   concentrado en los polígonos convexos para hacer el recorte (clipping)               más eficiente. El esquema del bucle interno de bloques descrito en                   fatmap.txt, ahora ha sido realizado en un bucle interno de 6 ciclos                  de reloj que se ha puesto en acción con buenos resultados.                                                                                                                Como en el documento previo, los bucles internos en ensamblador                      están desarroyados para el procesador Intel Pentium.                                                                                                                      La gente que esta buscando descripciones sobre los mapeadores de                     texturas con corrección de perspectiva deberían visitar el Game                      Developer Magazine en http://www.gdmag.com y encargar los                            numeros con los artículos de Chris Hecker sobre este tema!.                                                                                                               Yo, el autor, soy un viejo informático e ingeniero de telecomunicaciones             de 25 años (B.Sc.), actualmente trabajando como profesor en una                      escuela vocacional para alumnos de 16 a 19 años estudiando ordenadores,              electrónica, automatización y energía eléctrica. Hago graficos 3D en                 tiempo principalmente como un hobby, y soy un miembro activo del                     grupo Finlandes de demos Doomsday. Mi sueño es un día trabajar todo                  el tiempo con gráficos 3D.                                                                                                                                                Gracias especialmente a Harriet Mattfolk por la prelectura de este                   documento y ayudarme con la sintaxis inglesa.                                                                                                                                                                                                                                                                                                                                                                                      φ  2.  Aviso                                                                         φ  ----------                                                                                                                                                                   El autor no acepta ninguna responsabilidad, si algo en este documento                o los fuentes o ejecutables que lo compañan, producen alguna perdida                 de datos o daños en tu equipo.                                                                                                                                                                                                                                                                                                                                                                                                     φ  3.  Sobre el codigo fuente                                                        φ  ---------------------------                                                                                                                                                  Excepto por los bucles internos y otras funciones varias, el codigo                  esta escrito en C++ muy cercano al C. Para realizar la mayoría del                   codigo he hecho los bucles internos en ensamblador en línea.                         Personalmente tengo las funciones principales de mapeado en un                       ensamblador optimizado, pero sería poco logico incluir mucho de                      estos fuentes en este tipo de documento.                                                                                                                                  El codigo fuente que debería acompañar a este documento esta dividido                en 8 ficheros:                                                                                                                                                                misc.h      - Varias declaraciones de estructuras y funciones                                                                                                             clip.cpp    - Recorte 2D de Sutherland-Hodgman                                       draw.cpp    - Calcula deltas, recortes y llama a los mapeadores                      main.cpp    - Programa simple de test                                                                                                                                     flat.cpp    - Rellenado flat                                                         gouraud.cpp - Rellenado gouraud                                                      txtmap.cpp  - Mapeador de texturas                                                   txtarb.cpp  - Mapeador de texturas de cualquier tamaño                               txttil.cpp  - Mapeador de texturas en bloques                                                                                                                         Los últimos cinco ficheros son los interesantes. Los otros ficheros                  se han incluido para poder hacer el programa de text. Clip.cpp es                    mi propia implementación del algoritmo Sutherland-Hodgman y debería ser              de algun interés. Puedes encontrar la teoría del algorimo Sutherland-                Hodgman en cualquier libro de textos sobre gráficos.                                                                                                                      De un tiempo a un tiempo, he visto gente buscar una manera rápida                    de rellenar polígonos con un color sólido. Por lo tanto he incluido                  el rellenado flat. Tu podrías reemplazar la llamada a memset() por                   cualquier otro bucle interno. Recientemente he participado en un                     debate en el grupo de noticias comp.graphics.algorithms concerniente                 a coma flotante vs coma fija en un rellenado gouraud, por lo que he                  decidido incluir muy versión de rellenado gouraud.                                                                                                                        El fuente debería ser compilado con Watcom C/C++ ya que el ensamblador               en linea es específico de Watcom. No ha sido probado con la versión                  10.0 de Watcom C/C++. La versión compilada del programa de prueba                    (main.exe) va incluida. Necesitarás el DOS4GW protected mode para                    ejecutarlo.                                                                                                                                                                                                                                                                                                                                   φ  4.  Poligonos convexos                                                            φ  -----------------------                                                                                                                                                      Primero, definamos lo que es un poligono convexo. Un poligono convexo                no debe tener ninguno de sus esquinas apuntando al centro del poligono.              En otras palabras, el angulo entre dos lados formando un vertice no                  deben ser mayores que 180 grados. Esto significa que los triangulos son              siempre poligonos convexos. El opuesto de convexo, es concavo y pueden               tener esquinas apuntando hacia adentro.                                                               ______         ______________     ____        ____                        /\       /        \      \              /   |     \    /     |                     /   \    /            \      \           /    |       \/       |                   /      \   \            /      /          /     |                |                 /_________\    \ ______ /      /__________ /      |________________|                                                                                                        convexo        convexo         concavo               concavo                                                                                                            Los mapeadores presentados en este documento solo pueden dibujar                     poligonos con una excepcion. El tercer polígono de arriba puede                      ser manejado apropiadamente aunque sea concavo. Esto es porque aunque                sea concavo ningun scanline debe ser dividido cuando se renderiza.                   El cuarto polígono, no puede ser manejado apropiadamente porque                      habría que dividir scanlines.                                                                                                                                                                                                                            φ  5.  Dibujar poligonos convexos                                                    φ  -------------------------------                                                                                                                                              Dibujar poligonos convexos es tan simple y rapido como dibujar                       triangulos. La unica diferencia es que el codigo del vertice explorado               debe estar en un bucle interno para poligonos. Si nosotros solo                      renderizamos triangulos, sabemos que estos siempre tiene 3 vertices                  lo cual hace el codigo un poco mas sencillo.                                                                                                                              El primer paso en la funcion de poligonos es localizar los vertices de               arriba hacia abajo. Entonces nosotros esploraremos la tabla de vertices              y buscaremos la y minima y maxima. Cojamos el siguiente poligono de                  4 vertices como ejemplo:                                                                                                                                                                     v1                                                                                  / \                                                                                /      \                                                                           /           \                                                                      /                \                                                              v2 /                    / v0                                                            \                 /                                                                   \             /                                                                       \         /                                                                           \     /                                                                               \ /                                                                                  v3                                                                                                                                                          Notar que los vertices deben estar ordenados en sentido antihorario.                 Hemos encontrado que v1 es el vertices superior y v3 el inferior.                                                                                                         Ahora sabemos que cuando exploremos el lado izquierdo del poligono,                  deberíamos empezar en v1 y movernos hacia delante a traves de la tabla               hasta que llegasemos a v3. Generalmente, cuando avanzamos, deberiamos                volver al comienzo de la tabla si nos pasamos de ella. P.e. si                       llegamos al ultimo vertice, el siguiente sera el v0.                                                    v1                                                                                  /                                                                                  /                                                                                  /                                                                                  /                                                                               v2 /                                                                                    \                                                                                     \                                                                                     \                                                                                     \                                                                                     \                                                                                    v3                                                                                                                                                          Para el lado derecho empezamos en v1 y retrocedemos a traves de la                   tabla hasta que lleguemos a v3.. Generalmente cuando retrocedemos,                   deberíamos volver al final de la tabla sin nos pasamos. P.e. cuando                  llegamos a v0 nuestro proximo vertice será el ultimo en la tabla.                                                                                                                            v1                                                                                    \                                                                                       \                                                                                       \                                                                                       \                                                                                      / v0                                                                              /                                                                                 /                                                                                 /                                                                                 /                                                                                 /                                                                                  v3                                                                                                                                                          En nuestro ejemplo tenemos 2 secciones en el lado izquierdo:                                                                                                                v1 - v2   y  v2 - v3                                                                                                                                                    y 2 secciones en el derecho:                                                                                                                                                v1 - v0   y  v0 - v3                                                                                                                                                    El segundo paso en la funcion del poligono, es calcular el decremento de             la coordenada x para la primera sección en el lado derecho. Si la                    sección tiene de altura 0, prueba la siguiente hasta que encuentres                  una que no sea 0.                                                                                                                                                         El tercer paso es calcular el decremento de la coordenada x y cualquier              otro decremento (P.e. las coordenadas de textura u y v) para la primera              sección en el lado izquierdo. Si la sección tiene de altura 0, prueba                la siguiente hasta que encuentres una que no sea 0.                                                                                                                       Si todas las secciones de un lado tienen altura 0, el poligono                       tendrá una altura 0 y no deberá ser dibujado.                                                                                                                             Ahora podemos empezar a interpolar los valores a lo largo de los lados               izquierdo y derecho tal como dibujamos cada scanline usando un                       bucle interno.                                                                                                                                                                               v1                                                                                  /-\                                                                                /------\                                                                           /-----------\                                                                      /                \                                                              v2 /                     v0                                                                                                                                        Cuando llegamos al final de la seccion, buscaremos la siguiente                      sección con altura diferente de 0 y calcularemos el nuevo decremento.                Si todas las secciones del poligono estan listas, p.e. si hemos                      llegado al vertice inferior, el poligono esta acabado.                                                                                                                                                                                                                                                                                        φ  6.  Gradientes de textura constantes y poligonos                                  φ  -------------------------------------------------                                                                                                                            Con triangulos los gradientes de textura (las coordenadas de textura u               y v se decrementan a lo largo de la superficie del triangulo) esta                   garantizado que son constantes. Entonces podemos calcular los                        gradientes (dudx, dvdx) una vez y usar los mismos valores para                       todos los scanlines del triangulo.                                                                                                                                        Si empezamos con un triangulo y lo recortamos en un poligono, los                    gradientes de la textura permanecen constantes sobre toda la                         superficie. Entonces si calculamos los gradientes antes de recortar                  el triángulo podremos seguir usando el metodo de gradiente de textura                constante para los poligonos.                                                                                                                                             Calcular los gradientes de la textura para un triangulo puede hacerse                de la siguiente manera:                                                                                    v0                                                                                   /\                                                                                 /   \                                                                              /      \                                                                           /_________\                                                                        v1           v2                                                                                                                                                 double d = (v0.x - v2.x) * (v1.y - v2.y) -                                                      (v1.x - v2.x) * (v0.y - v2.y);                                            if(d == 0.0) return;                                                                 double id = 1.0/d * 65536.0;                                                         long dudx = ((v0.u - v2.u) * (v1.y - v2.y) -                                                      (v1.u - v2.u) * (v0.y - v2.y)) * id;                                    long dvdx = ((v0.v - v2.v) * (v1.y - v2.y) -                                                      (v1.v - v2.v) * (v0.y - v2.y)) * id;                                                                                                                     Los datos de los vertices x,y,u,v se asume que estan en coma flotante                y el resultado dudx, dvdx esta en coma fija 16:16.                                                                                                                                                                                                                                                                                            φ  7.  idiv e imul en coma fija 16:16                                                φ  -----------------------------------                                                                                                                                          Todos los mapeadores trabajan con coma fija 16:16 internamente. No                   explicare como trabaja la coma fija internamente, puede verser en                    cualquier sitio. Hare notar que necesitamos realizar las divisiones                  y multiplicaciones en ensamblador antes que en C. Entonces desde                     aqui puedes asumir que el codigo como:                                                                                                                                        long dxdy = (width << 16) / height;                                                  long x = v1.x + ((prestep * dxdy) >> 16);                                                                                                                             Debe realizarse con algunas funciones de ensamblador en linea:                                                                                                                long dxdy = idiv16(width, height);                                                   long x = v1.x + imul16(prestep, dxdy);                                                                                                                                                                                                                                                                                                    φ  8.  Funcion ceil() de coma fija                                                   φ  --------------------------------                                                                                                                                             Necesitamos una funcion ceil() para la precision de subpixel y subtexel.             Definicion de ceil() es:                                                                                                                                                      ceil(x) devuelve el menor entero no < x                                                                                                                                                                                                                    e.g.  ceil(1.0)  devuelve  1                                                               ceil(1.5)  devuelve  2                                                               ceil(-2.0) devuelve -2                                                               ceil(-1.5) devuelve -1                                                                                                                                              Si limitamos x solo a numeros positivos podemos hacer una version de                 ceil() en coma fija 16:16 muy facilmente. Sumaremos 0xffff a x y                     rotaremos hacia la derecha por 16.                                                                                                                                            inline long ceil(long x)                                                             {                                                                                        x += 0xffff;                                                                         return x >> 16;                                                                  }                                                                                                                                                                     Nota que esta funcion no da el resultado correcto si x es negativa.                  Esto no es problema ya que x nunca sera negativa de la manera en                     que ceil() se usa en los mapeadores.                                                                                                                                                                                                                                                                                                          φ  9.  Precision de subpixel                                                         φ  --------------------------                                                                                                                                                   La primera cosa a notar cuando pretendemos dibujar un poligono con                   precision de subpixel es que nunca debemos reducir las coordenadas                   de pantalla a integers. Hoy en dia es comun usar la coma flotante                    para todo en un motor 3D y convertir las coordenadas de pantalla                     proyectadas a integer justo antes de entrar en la funcion de poligonos.              Esta conversion, por supuesto, deberia ser de float a coma fija con                  lo que no perderiamos la parte fraccionaria. La parte fraccionaria es                de hecho la posicion del subpixel que afectara a como seran                          renderizados los incrementos en los lados del polígono.                                                                                                                   Sin la precisión de supixels los polígonos saltarán un pixel de golpe                cuando el objeto se mueva lentamente sobre la pantalla. Con precision                de subpixel los pixeles que hacen los lados entre polígonos flotaran                 lentamente, haciendo que los bordes parezcan moverse lentamente                      por pantalla.                                                                                                                                                             Calculando el decremento de una sección de precisión de subpixel:                                                                                                             long scanlines = ceil(v2.y) - ceil(v1.y);                                            if(scanlines <= 0) return;              // Sección con altura 0                                                                                                           long height = v2.y - v1.y;                                                           long dxdy = ((v2.x - v1.x) << 16) / altura;                                                                                                                               long prestep = (ceil(v1.y) << 16) - v1.y;                                            long left_x = v1.x + ((prestep * dxdy) >> 16);                                                                                                                        La altura de la sección, o el número de scalineas, serán un integer.                 Cuando calculamos el decremento (dxdy) no usaremos esa altura, es                    preferible usar la altura real que incluye la parte fraccionaria.                    Aplicamos la precisión de subpixel al decremento ajustando la coordenada             x inicial por el total que ha sido quitado cuando seleccionamos la                   coordenada y superior usando ceil();                                                                                                                                      Interpolar a lo largo de las secciones de precisión de subpixel                      izquierda y derecha:                                                                                                                                                          for(  )                                                                              {                                                                                        long x1 = ceil(left_x);               // Empieza scanline x                          long width = ceil(right_x) - x1;      // Ancho del scanline                                                                                                               if(width > 0)                                                                        {                                                                                        Ahora dibuja el scanline desde x1,y, con width pixels                                de ancho.                                                                        }                                                                                                                                                                         left_x  += left_dxdy;                                                                right_x += right_dxdy;                                                               y++;                                                                             }                                                                                                                                                                                                                                                                                                                                         φ  10. Precisión de subtexel                                                         φ  --------------------------                                                                                                                                                   Calcular los decrementos de u,v (dudy,dvdy) a lo largo de la sección                 de la misma manera que el decremento de la coordenada x y preparar                   los valores iniciales de la misma forma:                                                                                                                                      long height = v2.y - v1.y;                                                           long dudy = ((v2.u - v1.u) << 16) / height;                                          long dvdy = ((v2.v - v1.v) << 16) / height;                                                                                                                               long prestep = (ceil(v1.y) << 16) - v1.y;                                            long left_u = v1.u + ((prestep * dudy) >> 16);                                       long left_v = v1.v + ((prestep * dvdy) >> 16);                                                                                                                        Cuando interpolamos con precisión de subtexel debemos prepara u,v                    antes de dibujar cada scanline. Esto es porque redondeamos el                        comienzo del scanline (x1) hasta el punto más cercano usando ceil();                                                                                                          for(  )                                                                              {                                                                                        long x1 = ceil(left_x);                 // Empieza scanline x                        long width = ceil(right_x) - x1;        // Ancho del scanline                                                                                                             if(width > 0)                                                                        {                                                                                        long prestep = (x1 << 16) - left_x;                                                  long u = left_u + ((prestep * dudx) >> 16);                                          long v = left_v + ((prestep * dvdx) >> 16);                                                                                                                               Ahora dibujamos el escanline desde x1,y,u,v, con width                               pixels de ancho.                                                                 }                                                                                                                                                                         left_x  += left_dxdy;                                                                left_u  += left_dudy;                                                                left_v  += left_dvdy;                                                                right_x += right_dxdy;                                                               y++;                                                                             }                                                                                                                                                                                                                                                                                                                                         φ  11. Evitando divide overflow en calculo de decrementos                            φ  -------------------------------------------------------                                                                                                                      Para algunas secciones que son muy delgadas, el calculo del decremento               puede producir un overflow.                                                                                                                                               Mira el caso siguiente:                                                                                                                                                       v1.x = 0000:0000    v2.x = 0002:0000                                                 v1.y = 0000:0000    v2.y = 0000:0001                                                                                                                                  ceil(v2.y) - ceil(v1.y) devolverán que esto es un scanline excepto                   si la altura actual es justo la fracción de un pixel.                                                                                                                         height = v2.y - v1.y = 0000:00001                                                    width  = v2.x - v1.y = 0002:00000                                                                                                                                     entonces realizando (width << 16) / heigh) causará un divide overflow.               Estamos pretendiendo hacer un mapeado perfecto por lo que no podemos                 cojer un incremento por defecto para el decremento. Una manera de                    evitar el overflow es multiplicar el ancho (width) por la inversa                    de la altura (heigh) usando solo una precisión 18:14.                                                                                                                         long height = v2.y - v1.y;                                                           long inv_height = (0x10000 << 14) / height;                                          long dxdy = ((v2.x - v1.x) * inv_height) >> 14;                                                                                                                       Notase que este método solo puede ser usado para este caso especial                  donde la altura de la sección es menor que un pixel. Otras secciones                 que son mayores que un pixel deberían calcularse normalmente.                                                                                                                                                                                                                                                                                 φ  12. Contadores de bucles en bucles internos                                       φ  --------------------------------------------                                                                                                                                 Existe una forma ingenionsa de combinar el movimiento de un puntero                  destino y un contador de bucle en bucles interno. Puede no salvar mucho              (medio ciclo de reloj en un Pentium) pero puedes encontrar otras formas              de usarlo.                                                                                                                                                                Asume que queremos dibujar una línea horizontal en la pantalla con                   los siguientes datos:                                                                                                                                                         al  = color                                                                          ecx = ancho de la linea                                                              edi = puntero destino al primer pixel de la izquierda                                                                                                                 La forma normal sería:                                                                                                                                                        inner:                                                                                   mov   [edi], al         ; dibuja                                                     inc   edi               ; incrementa el puntero destino                              dec   ecx               ; decrementa el contador de bucle                            jnz   inner                                                                                                                                                       Otra forma es combinar el puntero destino y el ancho y dibujar la linea              desde la derecha hacia la izquierda.                                                                                                                                          inner:                                                                                   mov   [edi+ecx-1], al                                                                dec   ecx                                                                            jnz   inner                                                                                                                                                       En el bucle superior nos deshacemos de una instrucción. Sin embargo,                 estamos escribiendo en memoria desde una dirección alta a una baja.                  Esto es malo para los buffers de escritura. Deberíamos incrementar                   las direcciones en vez de decrementarlas. Esto puede hacerse de                      esta manera:                                                                                                                                                                      lea   edi, [edi+ecx]                                                                 neg   ecx               ; el contador va de -ancho a 0                                                                                                                inner:                                                                                   mov   [edi+ecx], al                                                                  inc   ecx                                                                            jnz   inner                                                                                                                                                       El destinatario es movido primera al final de la línea y el contador                 es negado. El primera pixel se dibujara en comienzo+ancho-ancho, o lo                que es lo mismo, al comienzo de la linea.                                                                                                                                         neg   ecx                                                                                                                                                         puede ser reemplazado por:                                                                                                                                                        xor   ecx, -1                                                                        inc   ecx                                                                                                                                                         El cual muchas veces puede ser emparejado con otras instrucciones en                 la situación del código. neg no es emparejable, 1 ciclo de reloj.                    Deberíamos acabar con:                                                                                                                                                            lea   edi, [edi+ecx]                                                                 xor   ecx, -1                                                                        inc   ecx                                                                        inner:                                                                                   mov   [edi+ecx], al                                                                  inc   ecx                                                                            jnz   inner                                                                                                                                                                                                                                                                                                                           φ  13. Bucle interno de 8:16 bit                                                     φ  ------------------------------                                                                                                                                               Despues de que fatmap.txt fuera publicado mandé un muy bonito bucle                  interno 8:16 de 4 ciclos de reloj hecho por Russel Simmons (Armitage                 /Beyond). En este original documento los scanlines son dibujados de                  derecha a izquierda. Estube una temporada en ello y presento aqui                    la nueva versión que dibuja los scanlines de izquierda a derecha.                                                                                                             ; bitmap (256x256) debe estar alineado con 64k. (16 bits bajos = 0)                  ; eax =  u frac           : -                                                        ; ebx =  bitmap ptr       : v int      : u int                                       ; ecx =  scanline width                                                              ; edx =  v frac           : v int step : u int step                                  ; esi =  u frac step      : 0          : 0                                           ; edi =  destination ptr                                                             ; ebp =  v frac step      : 0          : 0                                                                                                                                lea   edi, [edi+ecx]                                                                 xor   ecx, -1                                                                        inc   ecx                                                                                                                                                              inner:                                                                                  mov   al, [ebx]      ; obtener color                                                 add   edx, ebp       ; v frac += v frac step                                         adc   bh, dh         ; v int  += v int step (+carry de v frac)                       add   eax, esi       ; u frac += u frac step                                         adc   bl, dl         ; u int  += u int step (+carry de u frac)                       mov   [edi+ecx], al  ; dibujar pixel                                                 inc   ecx                                                                            jnz   inner                                                                                                                                                                                                                                                Esto es un buen bucle interno con la suficiente precisión, el cual                   puede encargarse de deformaciones de textura. Notese que la textura                  debe estar alineada sobre 64 Kb.                                                                                                                                          Una forma de alinear los mapas de texturas sobre 64 Kb es primero                    obetener un buffer con un largo mayor en 64 Kb que el mapa de texturas               y despues alinear el puntero dentro del buffer.                                                                                                                               char source[256*256];       // bitmap origen                                         char bigbuffer[256*256*2];  // 2*64k byte buffer                                                                                                                          char * aligned = (char *) (((int)(bigbuffer + 0xffff)) & ~0xffff);                   memcpy(aligned, source, 256*256);                                                                                                                                     Ahora se accede al bitmap usando el puntero alineado.                                                                                                                                                                                                                                                                                         φ  14. Bucles internos con bitmaps de cualquier tamaño                               φ  ----------------------------------------------------                                                                                                                         La idea para el siguiente bucle interno de 5 ciclos de reloj, fué                    obtenida de la subdivisión de scanlines en ek mapeador de texturas de                Chris Hecker. Este bucle no se fia en el hecho de que las texturas                   tengan siempre 256x256 pixels. Usamos una tabla de 2 dword en vez                    de realizar la multiplicación de v por el ancho. Por lo tanto puede                  trabajar con mapas de cualquier tamaño. La parte fraccionaria en                     este bucle puede ser de hasta 32 bits aunque solo usemos 16 bits aqui.               Notese que el bitmap no tiene que estar alineado.                                                                                                                         El truco en este bucle es convertir el flag de carry desde la parte                  fraccionaria de la suma de v en un índice en la tabla. Entonces                      obtiene el incremento de la textura desde la tabla.                                                                                                                           ; el bitmap puede tener cualquier tamaño                                             ; calcula la tabla duvdxstep de acuerdo con el ancho                                 ; dvdxfrac =  v frac step : 0                                                        ; eax =  u frac           : 0                                                        ; ebx =  v frac           : 0                                                        ; ecx =  scanline width                                                              ; edx =  u frac step      : 0                                                        ; esi =  bitmap ptr                                                                  ; edi =  destination ptr                                                                                                                                                  lea   edi, [edi+ecx]                                                                 xor   ecx, -1                                                                        add   ebx, [dvdxfrac]               ; v frac += v frac step                          inc   ecx                                                                            sbb   ebp, ebp                      ; -1 si carry desde add                                                                                                            inner:                                                                                  add   eax, edx                      ; u frac += u frac step                          mov   bl, [esi]                     ; obtiene el color                               adc   esi, [duvdxstep+4+ebp*4]      ; mueve el puntero a la textura                  add   ebx, [dvdxfrac]               ; v frac += v frac step                          sbb   ebp, ebp                      ; -1 si carry desde add                          mov   [edi+ecx], bl                 ; dibuja el pixel                                inc   ecx                                                                            jnz   inner                                                                                                                                                                                                                                                La tabla dudvxstep puede hacerse de la siguiente manera:                                                                                                                      long duvdxstep[2];                                                                                                                                                        duvdxstep[0] = (dudx >> 16) + (dvdx >> 16) * anchomapa + anchomapa;                  duvdxstep[1] = (dudx >> 16) + (dvdx >> 16) * anchomapa;                                                                                                               Esto significa que cuando obtener el carry de la suma de v y ebp                     se vuelve -1, direccionaremos dudvxstep[0] y sumaremos una linea                     extra en el bitmap.                                                                                                                                                       Un inconveniente de este bucle interno es que no puede realizar                      deformaciones de textura. Es decir, nunca puedes situar las coordenadas              u, v fuera del mapa de la textura o leera datos fuera del mapa                       de textura o causara una protection fault.                                                                                                                                                                                                                                                                                                    φ  15. Bucle interno de bloques en 8:15                                              φ  -------------------------------------                                                                                                                                        En fatmap.txt describía un método para colocar el mapa de textura                    como bloques de 8x8 para un uso más eficiente del caché. Entonces no                 conocía ninguna forma de hacer el bucle de cambio de bit en menos de                 11 ciclos de reloj. Pero un día se me ocurrió y escribí inmediatamente               una versión de 8 ciclos de reloj en 8:16. Esta versión en teoría no                  funcionaba pero un comienzo. El bucle interno inferior fue desarrollado              a partir de la versión original de 8 ciclos en un periodo de 2 meses.                Fue desarrollado solo en un papel la primera vez que probaba cualquiera              de los bucles, era esta versión y funcionó perfectamente.                                                                                                                 La versión inferior funciona en 6 ciclos de reloj y usa una                          interpolación de 8:15 bits. Aqui los bloques de 8x8 son usados puero                 cualquier tipo de esquema puede usarse, solo modificando las mascaras                de los bits. El bitmap de 256x256 no necesita estar alineado, pero                   para que el esquema de bloques sea efectivo el bitmap debería estar                  alineado sobre 32 bytes. Permite la deformación de texturas.                                                                                                                  ; el bitmap (256x256) debe estar almacenado en bloques de 8x8                        ; tildudx =  wwwww11111111www1fffffffffffffffb  (w=whole, f=frac)                    ; tildvdx =  11111wwwwwwww1111fffffffffffffffb                                       ; eax =  u   wwwww00000000www0fffffffffffffffb                                       ; ebx =  v   00000wwwwwwww0000fffffffffffffffb                                       ; ecx =  ancho del scanline                                                          ; edi =  puntero destino                                                             ; esi =  puntero al bitmap                                                                                                                                                lea   edi, [edi+ecx-1]                                                               xor   ecx, -1                                                                        lea   ebp, [eax+ebx]                            ; u+v                                inc   ecx                                                                                                                                                              inner:                                                                                  add   eax, [tildudx]                            ; u += tildudx                       add   ebx, [tildvdx]                            ; v += tildvdx                       shr   ebp, 16                                   ; (u+v) >> 16                        and   eax, 11111000000001110111111111111111b    ; borra huecos                       and   ebx, 00000111111110000111111111111111b                                         inc   ecx                                                                            mov   dl, [esi+ebp]                             ; obtiene el color                   lea   ebp, [eax+ebx]                            ; u+v                                mov   [edi+ecx], dl                             ; dibuja el pixel                    jnz   inner                                                                                                                                                                                                                                                Convertir dudx, dvdx en coma fija 16:16 al formato de boques                         puede hacerse de la siguiente manera:                                                                                                                                         tildudx = (((dudx << 8) & 0xf8000000) +                                                         ((dudx >> 1) & 0x00007fff) +                                                          (dudx       & 0x00070000)) | 0x07f88000;                                                                                                                      tildvdx = (((dvdx << 3) & 0x07f80000) +                                                         ((dvdx >> 1) & 0x00007fff)) | 0xf8078000;                                                                                                                  Notese que rellenamos los huecos en los bits con 1. Esto es porque                   debemos forzar a los bits a saltar sobre los huecos cuando sumemos                   en el bucle interno. Esos unos se borrarán despues de la suma. Hacemos               esto con las instrucciones and en el bucle interno.                                                                                                                       Antes de entrar en el bucle interno debemos convertir u,v al                         formato de bloques:                                                                                                                                                           u = ((u << 8) & 0xf8000000) +                                                            ((u >> 1) & 0x00007fff) +                                                             (u       & 0x00070000);                                                                                                                                              v = ((v << 3) & 0x07f80000) +                                                            ((v >> 1) & 0x00007fff);                                                                                                                                          Debería notarse que solo 15 bits son usados para la parte fraccionaria               y que es rotada hacia la derecha un bit. Esto es asi porque no debemos               dejar que la parte fraccionaria produzca un overflow y llene el                      puntero a la textura cuando sumemos u+v usando la instucción lea.                    Hemos añadido un huevo entre la parte fraccionaria y la parte principal              para evitar eso.                                                                                                                                                          El propio bitmap puede ser "ablocado" de la siguiente manera:                                                                                                                 char source[256*256];   // bitmap lineal de origen                                   char tiled[256*256];                                                                                                                                                      for(int v=0; v<256; v++) {                                                               for(int u=0; u<256; u++) {                                                               int dst = ((u<<8) & 0xf800)+(u & 0x0007)+((v<<3) & 0x07f8);                          tiled[dst] = source[u+v*256];                                                    }                                                                                }                                                                                                                                                                                                                                                                                                                                         φ  16. Poligonos por segundo                                                         φ  --------------------------                                                                                                                                                   De un tiempo a un tiempo he visto coders hablando sobre la velocidad                 de sus motores 3D especificando cuandos polígonos por segundo puede                  dibujar, esto es completamente irrelevante desde que no especifican                  bajo que condiciones han hecho ese test. La velocidad puede depender                 muchi del tamaño y orientación de los polígonos tanto como la forma                  en que los poligonos son texturados. Otros factores puedes contribuir                a la velocidad, como el tipo de administrador de memoria o el                        extensor de DOS.                                                                                                                                                          Con el simple programa de test que acompaña a este documento intendo                 comparar la velocidad entre los diferentes mapeadores. En este caso                  la comparación es válida porque trabajan exactamente bajo las mismas                 condiciones. Consigo los siguientes resultados en mi Pentium 120:                                                                                                             Flat                        3494                                                     Gouraud                     1849                                                     Texturas 256x256            1214                                                     Cualquier tamaño en textura 1196                                                     Texturas por bloques        1520                                                                                                                                      Esas figuras no son muy impresionantes, pero recordar que los                        triángulos pueden tener cualquier largo como lo permita x,y en el                    rango [0...320],[0...200]. En cualquier caso deberías notar que el                   rellenado flat (usando el standard memset() en el bucle interno) es                  como un par de veces más rápido que el resto. El mapeador con textura                de tamaño variable y el mapeador normal deberían ejecutarse a la                     misma velocidad. El mapeador por bloques aparece como el ganador                     porque permitimos a los valores u,v variar a lo largo de la superficie               del triángulo, es decir, que los capitulos sobre cachés se volveran                  mas importantes que una precálculo o un bucle interno rápido.                                                                                                                                                                                                                                                                                                                                                                      φ  17. Saludos                                                                       φ  ------------                                                                                                                                                                 Members de Doomsday                                                                  Members de SoCS                                                                      Members de Esteem                                                                    Phil Carmody                                                                         Nix / The Black Lotus                                                                Submissive / Cubic Team & $eeN                                                       Armitage / Beyond                                                                    Jare / Iguana                                                                        Wog / Orange                                                                         #coders. Ninguno mencionado, ninguno olvidado.                                       A todos mis estudiantes en YiJ 1996-1997; Data3, AD2, Elm2, El1A, El1B                                                                                                    ...mi corazon en Oslo                                                                                                                                                 .fdf (eof :).